package dp.背包01;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 一和零474.java
 * @createTime 2024年04月25日 14:33:00
 */
public class 一和零474 {
	/*
	转化为背包问题，大小为m体积为n的背包，装一组每个价值为1的东西的数组val[str.length][2]，
	定义函数dp[k][i][j]表示，前k件物品当前大小为i体积为j的情况下，最大价值和
	状态：
	如果第k个位置不进行选择
	dp[k][i][j]=dp[k-1][i][j]
	如果第k个位置进行选择
	dp[k][i][j]=dp[k-][i-val[k][0]][j-val[k][1]]+1
	,sum[k][0]是第k个数中0出现次数，sum[k][1]是第k个数中1出现的次数

	baseCase：
	考虑每个位置作为第一个选择的数的情况下，0和1的数量是否超过m和n
	 */
	public static int findMaxForm(String[] strs, int m, int n) {
		//表示每个数组的0 和 1 的个数
		int[][] val = new int[strs.length][2];
		//计算字符串每个位置的0 和 1的个数
		for (int i = 0; i < strs.length; i++) {
			String str = strs[i];
			int zero = 0, one = 0;
			for (char c : str.toCharArray()) {
				if (c == '0') {
					zero++;
				} else {
					one++;
				}
			}
			val[i][0] = zero;
			val[i][1] = one;
		}
		//处理字符串每个位置中0和1超标的情况
		int[][][] dp = new int[strs.length][m + 1][n + 1];
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= n; j++) {
				if (i < val[0][0] || j < val[0][1]) {
					dp[0][i][j] = 0;
				} else {
					dp[0][i][j] = 1;
				}
			}
		}
		for (int k = 1; k < strs.length; k++) {
			for (int i = 0; i <= m; i++) {
				for (int j = 0; j <= n; j++) {
					int noChoose = dp[k - 1][i][j];
					int choose=0;
					//选择第k个数，需要校验1和0 是否超标
					if (val[k][0] <= i && val[k][1] <= j) {
						choose=dp[k-1][i-val[k][0]][j-val[k][1]]+1;
					}
					dp[k][i][j]=Math.max(noChoose,choose);
				}
			}
		}
		return dp[strs.length-1][m][n];
	}

	public static void main(String[] args) {
		System.out.println(findMaxForm(new String[]{"10","0001","111001","1","0"},5,3));
	}
}
